"""
    create by IAmFiveHigh on 2024/7/31
"""
import math
import random


class MaxHeap:
    def __init__(self):
        self._data_array = []
        self._size = 0

    @classmethod
    def heapify(cls, arr):
        heap = cls()
        if len(arr) == 1:
            heap.add(arr[0])
        elif len(arr) > 1:
            heap._data_array = arr
            heap._size = len(arr)
            # 从最后一个有子结点的index开始到index == 0
            for i in range(heap._parent_index(len(arr) - 1), -1, -1):
                # 做siftdown
                heap._sift_down(i)
        return heap

    def get_size(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._size == 0

    def __getitem__(self, item: int):
        if item >= self._size:
            raise Exception("Error: 堆中当前位置无元素")
        return self._data_array[item]

    # 获取父节点index
    @staticmethod
    def _parent_index(index: int) -> int:
        if index == 0:
            raise Exception("Error: 堆的头节点没有父节点")
        # 因为头结点是0， 如果头结点从1开始那么就是 int(index / 2)
        return math.floor((index - 1) / 2)

    # 获取左孩子结点index
    @staticmethod
    def _left_child(index: int) -> int:
        # 因为头结点是0， 如果头结点从1开始那么就是 index * 2
        return index * 2 + 1

    # 获取右孩子结点index
    @staticmethod
    def _right_child(index: int) -> int:
        # 因为头结点是0， 如果头结点从1开始那么就是 index * 2 + 1
        return index * 2 + 2

    # 添加元素
    def add(self, element):
        self._data_array.append(element)
        self._size += 1
        #  添加元素后要符合父节点元素大于子结点
        self._sift_up(self._size - 1)

    def _sift_up(self, index: int):
        i = index
        while i != 0:
            # 获取父节点index
            parent_index = self._parent_index(i)
            # 如果当前结点元素比父节点大
            if self._data_array[i] > self._data_array[parent_index]:
                # 交换父节点和当前结点元素
                self._exchange(i, parent_index)
                # 当前结点修改为父节点，继续下一次循环
                i = parent_index
            else:
                # 当前结点元素比父节点小，循环结束
                break

    # 交换数组中两个位置的元素
    def _exchange(self, l, r):
        if l < 0 or l >= self._size or r < 0 or r >= self._size:
            raise Exception("Error: 交换的索引位置的元素为空")
        temp = self._data_array[l]
        self._data_array[l] = self._data_array[r]
        self._data_array[r] = temp

    # 看一眼最顶端元素
    def find_max(self):
        if self.is_empty():
            raise Exception("Error: 当前堆是一个空堆")
        return self.__getitem__(0)

    # 提取顶端元素
    def extract_max(self):
        # 保存头元素
        ret = self.find_max()
        # 交换最末尾的元素和头元素
        self._exchange(0, self._size - 1)
        # 删除头元素(因为交换过了头尾所以pop就是删除头)
        self._data_array.pop()
        self._size -= 1

        # 把交换过来的尾元素下沉
        self._sift_down(0)

        return ret

    def _sift_down(self, index):
        i = index
        # 如果左孩子的index还没超出size，说明左孩子还存在，当前index不是叶结点
        while self._left_child(i) < self._size:
            k = self._left_child(i)
            # 如果有右孩子， 同时右孩子元素比左孩子大，那么把k赋值为右孩子的索引，否则保持为左孩子的索引
            if k + 1 < self._size and self._data_array[k + 1] > self._data_array[k]:
                k = self._right_child(i)
            # 这时候dataArray[k]是当前index左右子结点元素中最大值

            # 如果子孩子的最大值比当前index的值大那么交换他们
            if self._data_array[k] > self._data_array[i]:
                self._exchange(i, k)
                i = k
                # 进入下一轮循环
            else:
                # 否则结束循环
                break

    #  顶端元素替换为新元素
    def replace(self, element):
        if self._size < 1:
            return

        ret = self.find_max()
        self._data_array[0] = element
        self._sift_down(0)
        return ret

    def __str__(self):
        return self._data_array.__str__()

if __name__ == '__main__':
    # 测试实现的最大堆

    mh = MaxHeap()
    for i in range(10000):
        mh.add(random.randint(0, 10000))

    ret_list = []
    for i in range(10000):
        ret_list.append(mh.extract_max())

    for i in range(1, 10000):
        if ret_list[i - 1] < ret_list[i]:
            raise Exception("Error: 实现的最大堆有问题，每次吐出的最大值并不是最大")
    print("实现的最大堆没有问题")

    # 测试heapify方法
    l1 = [1, 2, 3, 4, 5]
    heap = MaxHeap.heapify(l1)
    if heap.__str__() == [5, 4, 3, 1, 2].__str__():
        print("实现的list的heapify方法没有问题")
    else:
        print("list的heapify出错")